package com.code.snippet.floyd;
/*https://www.iteye.com/blog/bylijinnan-1377758
* https://blog.csdn.net/qq_34842671/article/details/90637502
* */
public class FloydGraph<T> {
    public int NR = 100000;//此路不通
    private T[] datas;  // 保存每个节点的数据
    private int N; // N个节点
    public int[][] matrix;  // 邻接矩阵
    public int[][] path;//中间节点
    public String[][] nodePath;
    public FloydGraph(T[] datas) {
        //datas = (T[]) new Object[N];  // 泛型数组实例化
        this.datas = datas;
        this.N = datas.length;
        matrix = new int[N][N];
        nodePath = new String[N][N];
        path = new int[N][N];
    }

    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }
    //public void setMatrix(int from, int to, int weight) {matrix[from][to] = weight;}

    //public void setDatas(T[] datas) { this.datas = datas; }

    //非递归实现
    public void floyd() {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                path[i][j] = -1;
            }
        }

        for (int m = 0; m < matrix.length; m++) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    if (matrix[i][m] + matrix[m][j] < matrix[i][j]) {
                        matrix[i][j] = matrix[i][m] + matrix[m][j];
                        //记录经由哪个点到达
                        path[i][j] = m;
                    }
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                nodesInPath="";
                if (i != j) {
                    if (matrix[i][j] == NR) {
                        System.out.println(i + "到" + j + " " +datas[i] + "-"+datas[j]+ "不可达");
                    } else {
                        System.out.print(i + "到" + j + " " +datas[i] + "-"+datas[j]+"的最短路径长度是：" + matrix[i][j]);
                        System.out.print("最短路径为：" + datas[i] + "" + i + "->");
                        nodesInPath =datas[i] + "-";
                        findPath(i, j);
                        nodesInPath +=datas[j];
                        System.out.println(datas[j] + "" + j);
                        nodePath[i][j]=nodesInPath;
                    }
                }
            }
        }
        System.out.println();
        System.out.println("path,记录经由哪个点到达");
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                //System.out.print(path[i][j] + ",");
                System.out.print(String.format("%1$5s", path[i][j]));
            }
            System.out.println();
        }
        System.out.println();
        System.out.println("matrix,最终矩阵");
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int d=matrix[i][j];
                if(matrix[i][j] == NR){d=0;}
                System.out.print(String.format("%1$5s", d));
            }
            System.out.println();
        }
        System.out.println();
        System.out.println("nodePath,路径");
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                System.out.print(String.format("%1$20s", nodePath[i][j]));
            }
            System.out.println();
        }
        System.out.println();
    }

    //递归寻找路径
    private String nodesInPath;
    public void findPath(int i, int j) {
        int m = path[i][j];
        if (m == -1) {
            return;
        }
        findPath(i, m);
        System.out.print(datas[m] + "" + m + "->");
        nodesInPath +=datas[m] + "-";
        findPath(m, j);
    }

    public static void main(String[] args) {
        int NR = 100000;

        String[] nodes=new String[]{"A", "B", "C", "D", "E"};
        int[][] matrix={
                {NR,30,NR,10,50},
                {NR,NR,60,NR,80},
                {NR,NR,NR,NR,NR},
                {NR,NR,NR,NR,30},
                {NR,NR,40,NR,NR},
        };

//        String[] nodes=new String[]{"A", "B", "C", "D", "E","F","G"};
//        int[][] matrix={
//                {NR,6,NR,2,NR,NR,NR},
//                {NR,NR,5,NR,NR,3,NR},
//                {NR,NR,NR,NR,NR,NR,NR},
//                {NR,7,NR,NR,5,NR,NR},
//                {NR,NR,NR,NR,NR,NR,1},
//                {NR,NR,3,NR,2,NR,NR},
//                {NR,NR,NR,NR,NR,NR,NR}
//        };

        FloydGraph<String> graph = new FloydGraph<>(nodes);
        //graph.setDatas(nodes);
        graph.setMatrix(matrix);
        graph.floyd();

        int i=3;
        int j=4;
//        System.out.println(nodes[i] +"-"+ nodes[j]+"最短路径:");
//        graph.findPath(3,4);
        System.out.print(nodes[i] +"-"+ nodes[j]+" >  nodePath路径:" + graph.nodePath[i][j]);
        System.out.println("  距离:" + matrix[i][j]);

    }

}
